package com.sheng.leetcode.year2023.month10.day14;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author by ls
 * @date 2023/10/16
 * <p>
 * 136. 只出现一次的数字<p>
 * <p>
 * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。<p>
 * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。<p>
 * <p>
 * 示例 1 ：<p>
 * 输入：nums = [2,2,1]<p>
 * 输出：1<p>
 * <p>
 * 示例 2 ：<p>
 * 输入：nums = [4,1,2,1,2]<p>
 * 输出：4<p>
 * <p>
 * 示例 3 ：<p>
 * 输入：nums = [1]<p>
 * 输出：1<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 3 * 10^4<p>
 * -3 * 10^4 <= nums[i] <= 3 * 10^4<p>
 * 除了某个元素只出现一次以外，其余每个元素均出现两次。<p>
 */
public class LeetCode0136 {

    @Test
    public void test01() {
//        int[] nums = {2, 2, 1};
//        int[] nums = {4, 1, 2, 1, 2};
        int[] nums = {1};
        System.out.println(new Solution().singleNumber(nums));
    }
}

class Solution {
    public int singleNumber(int[] nums) {
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length; i += 2) {
//            if (i == nums.length - 1) {
//                return nums[i];
//            }
//            if (nums[i] != nums[i + 1]) {
//                if (nums[i + 1] == nums[i + 2]) {
//                    return nums[i];
//                }
//            }
//        }
        /*
          异或计算
          任何数和 0 做异或运算，结果仍然是原来的数，即 a ^ 0 = a 。
          任何数和其自身做异或运算，结果是 0，即 a ^ a = 0 。
          异或运算满足交换律和结合律，即 a ^ b ^ a = b ^ a ^ a = b ^ (a ^ a) = b ^ 0 = b。

          作者：力扣官方题解
          链接：https://leetcode.cn/problems/single-number/
          来源：力扣（LeetCode）
          著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */
        return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
    }
}
